﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0159_ProductExceptSelf : IAlgorithm
    {
        // 238. 除自身以外数组的乘积

        // 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

        // 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
        // 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

        // 提示：
        //  2 <= nums.length <= 10^5
        //  -30 <= nums[i] <= 30
        //  保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内

        // 进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

        public void Test()
        {
            // 算法参数定义
            var nums = new int[] { 0, 1, 3, 4, 2 };
            // 算法执行与打印
            var res = ProductExceptSelf(nums);
            foreach (var item in res)
            {
                Console.Write(item + " ");
            }
        }

        // 算法
        //输入: nums = [1,2,3,4]
        //输出: [24,12,8,6]
        public int[] ProductExceptSelf(int[] nums)
        {
            int zeroCnt = 0, baseVal = 1;
            for (int i = 0; i < nums.Length; i++)
                if (nums[i] == 0)
                    zeroCnt++;
                else
                    baseVal *= nums[i];

            if (zeroCnt > 1)
            {
                Array.Fill(nums, 0);
                return nums;
            }

            for (int i = 0; i < nums.Length; i++)
                if (zeroCnt == 1)
                    if (nums[i] != 0)
                        nums[i] = 0;
                    else
                        nums[i] = baseVal;
                else
                    nums[i] = baseVal / nums[i];
            return nums;
        }
    }
}
